package com.torlesse.leetcode.algorithm.common;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: torlesse-liang
 * @Date: 2022/03/04/22:17
 * @Description: 选择排序
 */
public class SelectSort {
    public static void main(String[] args) {
//        selectSort(Swap.array);
        selectSort2(Swap.array);
        Swap.print(Swap.array);
    }

    /**
     * 选择排序
     * 思想：每次排序选出最小值 然后进行交换
     * @param array
     */
    public static void selectSort(int[] array){
        for (int i = 0; i < array.length - 1; i++) {
            //记录最小元素位置 pos
            int pos = i;
            for (int j = i; j < array.length - 1; j++) {
                if(array[pos] > array[j]){
                    pos = j;
                }
            }
            Swap.swap(array,i,pos);
        }
    }

    /**
     * 改进
     * 每一次最小 最大元素归位
     * @param array
     */
    public static void selectSort2(int[] array){
        int len = array.length - 1;
        for (int i = 0; i <= len; i++) {
            //记录最小元素位置 minPos
            int minPos = i;
            //记录最大元素位置 maxPos
            int maxPos = i;
            for (int j = i; j <= len; j++) {
                if(array[minPos] > array[j]){
                    minPos = j;
                }
                if(array[maxPos] < array[j]){
                    maxPos = j;
                }
            }
            //最小元素归位
            Swap.swap(array,i,minPos);
            //最大元素归位
            Swap.swap(array,len,maxPos);
            len --;
        }
    }
}
